The invention generally relates to the field of linear block codes. More particularly, the invention relates to a soft decision turbo product code decoder for error correction decoding.
Recently, error correction decoding techniques for recognizing and correcting errors in digital signal transmission have been used in many fields to improve the reliability of data transmission. One such technique is known as Error Corrective Coding (ECC). The basic concept of ECC is to add redundant bits to a digital message in order to eliminate the need for retransmission of the data. This addition of redundant bits to the message is known as Forward Error Correction (FEC). The addition of these redundancy bits allows a decoder at the receiving end to detect and/or correct errors that might have been caused during transmission.
There are several methods employed in adding redundant bits to a message, and one such method is known as block coding. In block coding, the data or message to be transmitted is broken into smaller blocks and each block is coded separatelyxe2x80x94i.e. redundant bits are appended to the end of each block of data. On the receiving end, each block of data is decoded separately. Block coding has been used in many practical applications, including magnetic and optical storage systems, as well as mobile communications systems, such as cellular phones. Familiarity with the terminology used in block coding is important in understanding the present invention. In preparation for the description contained herein, the basic principles and terminology behind block coding shall be briefly described.
A block code is often described as an (n,k) code, wherein n is the total number of bits in the encoded transmission block and k is the number of bits in the unencoded message block. Accordingly (nxe2x88x92k) redundancy bits, also known as parity bits, have been added to the message block when it is encoded before transmission. In a block code, every legitimate unencoded message differs from every other legitimate unencoded message by a minimum number of bit positions. We refer to this number of bit positions by which every legitimate unencoded message differs as the Hamming distance dmin. In order to correct single bit errors, a block code must have a minimum Hamming distance of at least 3.
Binary Hamming codes are a well known family of codes used in the art of error correction which provide FEC by using a xe2x80x9cblock parityxe2x80x9d mechanism, wherein a number of redundancy or parity bits are appended to each block of data before transmission. The number of parity bits required to be appended for a given block is defined as the Hamming rule, and is a function of the total number of bits which may transferredxe2x80x94i.e. the bandwidth. A code obtained by appending an (even) extended parity bit onto a binary Hamming code is called an extended Hamming code.
Product codes arrange two dimensional codes (n,k) into (nxc3x97n) size arrays. First, k blocks of data, with each block being a length k, are stored in a (kxc3x97k) array. Each row and column is then encoded with redundancy bits or ECC and the (even) extended parity bit is appended to each row and column, thereby creating an Extended Hamming Product code For example, the following diagram shows an (8,4)xc3x97(8,4) Extended Hamming Product Code, where xe2x80x9cDxe2x80x9d represents original data, xe2x80x9cExe2x80x9d represents the ECC or redundancy bits, and xe2x80x9cPxe2x80x9d represents the extended parity bit.
As can be seen, each row and column ends with a parity bit P.
The conventional method for decoding an Extended Product Hamming Code after transmission is to receive incoming data, store it in an array and decode each row or column of the array separately using maximum likelihood decoding. Typically, this is accomplished through the use of a look-up table which includes every legitimate valid message. In the decoding process, the data is compared to each entry in the look-up tablexe2x80x94i.e. all of the possible valid messages within the table, after the parity and redundancy bits have been removed. If the Hamming distance dmin is large, than the likelihood of error in choosing the right message from the table is reduced. However, if the Hamming distance dmin is small, then the likelihood of error increases. Full correlation decoding of one row or column in a product code requires comparing the data with the full set of possible transmitted codewords. For an (8,4) code, this only requires a comparison with 16 possible transmitted codewords. However, for a (64, 57) code, there are 1.4xc3x971017 possible transmitted codewords, making a full correlation with the use of a look-up table unfeasible.
Additionally, error correction decoding techniques acquire increased value when they not only accurately estimate the content of the original message; but, also provide confidence measures as to the likelihood that the decoded message is correct. Such information is generally referred to as xe2x80x9csoft output informationxe2x80x9d. As an example, in a soft output decoder, the decoder will receive an incoming block of data and attempt to decode the incoming block of data. After decoding the incoming block of data, the soft output decoder will assign a confidence value or measure to the output, indicating whether the decoder is. more or less certain of the results. If the decoder assigns a high confidence value to the output, it is more certain that is has properly decoded the incoming block of data. However, if the decoder assigns a low confidence value to the output, it is less certain that the incoming block of data has been properly decodedxe2x80x94i.e. there may be more than one possible interpretation of the incoming block of data.
A Soft In/Soft Out (SISO) decoder receives demodulated soft decision input data and produces soft decision output data. For each bit in the block of soft decision input data, the decoder examines the confidence of the other bits in the block, and using the redundancy of the code, generates a new soft decision output for the given bit. If the redundancy of the code indicates that the output for the given bit is correct, the decoder will output a positive confidence value. If the redundancy of the decode indicates that the output for the given bit is incorrect, it will output a negative confidence value. The negative value indicates that the confidence value for that bit should be decreased. This may mean that the bit should be inverted from a xe2x80x9c1xe2x80x9d to a xe2x80x9c0xe2x80x9d or vice versa.
Within the last decade, SISO decoders have been applied to a new decoding method called turbo codes. Turbo codes are an iterative decoding scheme which decode incoming data blocks in two or more dimensions (depending on the encoding scheme). Accordingly, by way of example, incoming data may be stored in an array and decoded by row and column. When the iterative decoding is applied to product codes of extended Hamming Codes the resultant code is called a turbo product code. A conventional turbo product decoder feeds demodulated soft decision data into the SISO for the first dimension (i.e. the x-rows). The output is then summed with the original demodulated soft decision data and fed back into the SISO for decoding of the second dimension (i.e. the y-columns). The output from the SISO is again summed with the original demodulated soft decision data and fed back into the SISO for decoding of the first dimension once again (i.e. the x-rows). In order for this iterative decoding process to be effective, the data must have been encoded in at least two different dimensions (i.e. it was stored in an array and the rows and columns of the array were each encoded). Typically, this is done by encoding the data horizontally (rows) and vertically (columns).
Typically, each iteration in the decoding process modifies the confidence or soft decision value assigned to each bit since the data is slightly modified through each horizontal and/or vertical decode iteration. This is usually done by generating a new confidence or soft decision value after each iteration. Eventually, the confidence or soft decision value will be pushed higher or lower until a hard decision value (bit value of 0 or 1) can be reached. This iterative process continues until a hard decision value for each bit is reached.
It is understood that when decoding in more than two dimensions, each dimension may be decoded using a different decoding scheme or algorithm (i.e. the rows and columns may not have necessarily been encoded using the same encoding scheme and, accordingly, a different decoding scheme may be used for decoding rows versus decoding columns). Moreover, if decoding in more than two dimensions, then each axis or dimension will be fully decoded before beginning again with the first axis (i.e. all x-rows will be decoded, then all y-columns will be decoded and, finally, all z-columns must be decoded before beginning the second full iteration). Thus, for example, when decoding a three dimensional scheme with an x-axis, a y-axis and a z-axis, the x-axis is first decoded. The results from the x-axis decoding are then summed with the original demodulated soft decision data and fed back into the decoder for decoding of the y-axis. The results from the y-axis decoding are then summed with the results from the x-axis and the original demodulated soft decision data, and the result if fed back into the decoder for decoding of the z-axis. Finally, after the z-axis has been decoded, the results from the z-axis decoding, the previous y-axis decoding results, the previous x-axis decoding results, and the original demodulated soft decision data are summed and the resultant is fed back into the decoder for decoding along the x-axis for a second iteration. Thus, between decoding of each axis the results for all previous decoding in other dimensions will be summed with the original demodulated soft decision data.
One problem which exists with this prior art technique is the recurring use of the original demodulated soft decision data. The fundamental principle for iterative decoding feedback is to avoid feedback which includes information which stems from the input. This is important because the error of any decoder will be highly correlated between future iterations if the feedback includes information which stems from the input. This prior art technique for turbo decoding continuously sums the output from each previous iteration with the original demodulated soft decision data, thereby increasing the likelihood of error in subsequent iterations. Accordingly, what is needed is a turbo decoding scheme which does not rely upon the previous iteration results in subsequent iterations.
Additionally, much like the product coding scheme described earlier, conventional turbo coding/decoding techniques rely heavily upon the use of look-up tables in order to generate valid xe2x80x9cnearest neighborsxe2x80x9d and assign soft decision values. Once again, full correlation decoding of each axis requires comparing the received soft decision data with the full set of possible transmitted codewords. As explained earlier, there are 2k possible codewords transmitted for an (n, k) code. Accordingly, in order to fully decode an (8,4) code, each individual axis would require a comparison with only sixteen transmitted codewords. However, for a (64,57) code, there are 1.4xc3x971017 possible transmitted codewords, making a full comparison with each possible codeword unfeasible. Some prior art decoders reduce the size of the look-up table but require a kxc3x97k size table. Accordingly, what is further needed is a decoding scheme which does not require the use of look-up tables to find the valid xe2x80x9cnearest neighborxe2x80x9d and assign soft decision values.
The turbo product code decoder of the present invention generates soft difference values, instead of new confidence values, in order to improve performance. The difference between prior art decoders and the present invention lies in the fact that these soft difference values have the soft decision value of the input subtracted from the confidence value output. After any full iterationxe2x80x94i.e. after all axis (x, y and z) dimensions have been decoded, the previous difference value for any axis is discarded when that axis is decoded in subsequent iterations. Accordingly, the same information is not continuously fed into the decoder during each subsequent iteration, thereby decreasing the likelihood of error and offering an improvement over prior art decoders.
Moreover, using unique nearest neighbor computation logic, the turbo product code decoder of the present invention is able to generate valid nearest neighbors more efficiently without requiring the use of a look-up table, thereby reducing the design size. Finally, the turbo product code decoder of the present invention utilizes four decoders arranged in parallel along with a unique array accessing scheme such that multiple rows or columns may be decoded at the same time, thereby increasing the data throughput time of the turbo product code decoder of the present invention over prior art turbo product code decoders.
The present invention is a turbo product code decoder capable of decoding multi-dimensional coding schemes. The turbo product code decoder of the present invention may be implemented in any digital communication system capable of receiving an encoded stream of data. The digital communication system will preferably include a conventional demodulator which receives the encoded stream of data, demodulates the encoded stream of data and generates an initial soft decision value for each bit in the encoded stream of data. This initial soft decision value may be in a signed or unsigned 2""s complement notation, with the sign (+) or (xe2x88x92) representing a determination as to whether the bit is a binary xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d and the numerical value representing an initial confidence level in such determination. These initial soft decision values are then output from the demodulator and fed into the turbo product code decoder of t he present invention.
When decoding a two dimensionally encoded schemexe2x80x94i.e. a stream of data which has an x-axis coding and a y-axis coding, the initial soft decision values are transmitted from the conventional demodulator to the turbo product code decoder of the present invention, where they are preferably deinterleaved and arranged into four soft value words which are stored in a two dimensional original memory array of x-rows and y-columns. The original memory array is preferably arranged in four ny rows each having nx/4 words per row, where nx and ny are the length of the x and y axes, respectively. The initial soft decision values are stored in the original memory array in four soft value words with each individual soft decision value being stored in the signed or unsigned two""s complement notation. As explained above, the absolute or numerical value represents an initial confidence level for each bit in the four vectors and the sign (+) or (xe2x88x92) represents an initial hard decision bit value determination as to whether the bit is a binary xe2x80x9c1xe2x80x9d or a binary xe2x80x9c0xe2x80x9d, wherein a (+) sign represents a bit value of xe2x80x9c1xe2x80x9d and a (xe2x88x92) sign represents a bit value of xe2x80x9c0xe2x80x9d.
The initial soft decision values in the x-rows of the original memory array, which represent the x-axis coding, are then read from the array into a SISO group which includes four separate SISO decoders arranged in parallel. These values are read from the original memory array on a row by row basis using a unique accessing scheme. This unique accessing scheme shall be described in greater detail; but, for now, it is understood that the initial soft decision values are accessed from the original memory array on a row by row basis such that four rows or column vectors can be decoded in parallel using the four SISO decodersxe2x80x94with each SISO decoding row or column vector.
These four SISO decoders utilize improved nearest neighbor computation logic to generate nearest neighbors for the four vectors in the codeword without using look-up tables. The xe2x80x9cclosestxe2x80x9d nearest neighbor is then selected by calculating a difference metric for each nearest neighbor and selecting the nearest neighbor having the lowest difference metric. Each bit in the xe2x80x9cclosestxe2x80x9d nearest neighbor is then assigned a xe2x80x9cdifferencexe2x80x9d value which is based upon a numerical difference between a new confidence value calculated for that bit and the confidence value assigned to the bit in the same position in the incoming vector.
After all four rows have been decodedxe2x80x94i.e. after a new difference value has been assigned to each bit in the xe2x80x9cclosestxe2x80x9d nearest neighbor, four entire vectors are generated with new difference values in each bit position. Each difference value is then multiplied by an x-axis feedback constant and the entire four rows are then stored by the data multiplexer in a temporary difference array. Each bit in the four output vector is stored in signed or unsigned two""s complement notation, with the numerical value in each bit position representing the change in confidence level and the sign (+) or (xe2x88x92) representing the degree of change. This process is repeated for all rows in the product code.
The information in the temporary difference array is then summed with the initial soft decision values which are stored in columns of the original memory array, thereby generating new input data which is then fed back into the SISO group for decoding by the four SISO decoders. Once again this is done using a unique accessing scheme which shall be discussed in greater detail herein; but, for now, it is understood that the initial soft decision values stored in the columns (the y-axis data) of the original memory array is read on a column by column basis where is summed with the information in the temporary difference array. Using this new input data, the y-axis data is decoded.
Once again, the four SISO decoders are used to generate nearest neighbors and the xe2x80x9cclosestxe2x80x9d nearest neighbor is again selected. Each bit in the closest nearest neighbor is then assigned a difference value based upon a difference between a new confidence value assigned to the bit and the confidence value of the bit in the same position in the new input data. Four new vectors are generated and each difference value in each output vector is multiplied by a y-axis feedback constant. The new output vectors are stored in the temporary difference array, overwriting the difference values for the output vector from the decoding of the rows which were previously stored after the x-axis iteration. This process is repeated for all columns in the product code.
The information in the temporary difference array is once again summed with the initial soft decision values stored in the rows of the original memory array (the x-axis data), and the result is fed back into SISO group on a row by row basis. This iterative process of decoding rows (x-axis), then columns (y-axis) and then rows (x-axis) is repeated between the rows (x-axis) and columns (y-axis), for k full iterations, wherein a full iteration represents a single pass through the decoder of both the x-axis (rows) and y-axis (columns).
After the final full iteration, the difference values in the new output vectors for the y-axis are multiplied by the y-axis feedback constant and, instead of being stored in the temporary difference array, these values are then summed with the information stored in the difference array (which should be the difference values from the previous x-axis iteration) and the initial soft decision values stored in the original memory array (original x-axis and y-axis data) in order to generate final output values. These final output values will be in a signed two""s compliment notation, with the sign representing the actual binary bit value of xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d and the numerical value representing a final confidence level. These final output values are then converted into a decoded output data stream of binary xe2x80x9c1""sxe2x80x9d and xe2x80x9c0""sxe2x80x9d.
The turbo product code decoder of the present invention can also be used to decoded data streams which have been encoded with three dimensional coding schemes or higher. For example, when decoding a three dimensional code, the initial soft decision values are transmitted from the conventional demodulator to the turbo product code decoder of the present invention, where they are deinterleaved and stored in the original memory array, with ny times nz rows with each row containing nx/4 words.
The decoding process proceeds in much the same way as a two dimensional scheme; however, when decoding a three dimensional code, the output from the two previous axis iterations are each stored in separate difference arrays and then summed with the initial soft decision data in order to generate the input for each subsequent iteration. For example, on the first iteration of decoding the x-axis, the output difference values will be multiplied by an x-axis feedback constant and stored in a first difference array. The information in the first difference array will then be summed with the initial soft decision values in the y-columns of the original memory array in order to generate the input values used for the y-axis iteration, and the y-axis iteration will begin.
Upon completion of the y-axis iteration, the output difference values which result from decoding the y-axis will be multiplied by a y-axis feedback constant and stored in a second difference array. Then, the information from the first difference array (the x-axis iteration difference values), the information in the second difference array (the y-axis iteration difference values), and the original incoming data will then all be summed in order to generate the input for the z-axis iteration. Once the z-axis has been decoded, the output from the z-axis iteration will be multiplied by a z-axis feedback constant and stored in the first difference array, overwriting the output from the prior x-axis iteration which was previously stored in the first difference array.
Subsequently, the information from the first difference array (the z-axis iteration results) and the second difference array (the y-axis iteration results) will then be summed with the original incoming data for the x-axis (which is stored in the first sixteen rows of the original memory array) in order to generate the input for the second x-axis iteration. Once the x-axis has been fully decoded for a second iteration, the output difference values are once again multiplied by the x-axis feedback constant and this time stored in the second difference array, overwriting the output from the previous y-axis iteration.
This process of iteratively decoding each axis continues with the output difference values from the SISO group being multiplied by the appropriate feedback constant and written, alternately, to the first and second difference arrays, such that as each axis is decoded, the previous results from the iterations of the other two axes are stored in the difference arrays.
The decoder can run a pre-programmed number of iterations, or it can determine when the decoding operation is completed using a stop iteration criteria. Using the status from each SISO, the decoder can determine that future iterations will not further modify the data. At this point, it completes one final iteration to sum all axes differences values with the initial soft decision values and generates a hard decision output.
After the final full iteration, when all axis (x, y and z) have been decoded, the output difference values from the final z-axis iteration are multiplied by the z-axis feedback constant and summed with the previous x-axis iteration difference values (which should still be stored in the first difference array), the previous y-axis difference values (which should still be stored in the second difference array) and the initial soft decision values stored in the original memory array, thereby generating final output values. These final output values will be in a signed two""s compliment notation, with the sign representing the actual binary bit value of xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d and the numerical value representing a final confidence level. These final output values are then converted into a decoded output data stream of binary xe2x80x9c1""sxe2x80x9d and xe2x80x9c0""sxe2x80x9d.